# -*- coding:utf-8 -*-
# Definition for singly-linked list.
import sys

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class List:
    def __init__(self, val=0):
        if val == None:
            self.val = '#'
        else:
            self.val = val


class Solution:
    def build(self, inorder: list, inStart: int, inEnd: int,
              postorder: list, postStart: int, postEnd: int) -> TreeNode:
        ##base case
        if inStart > inEnd: return None

        rootVal = postorder[postEnd]
        index = 0
        for i in range(inStart, inEnd + 1):
            if inorder[i] == rootVal:
                index = i
                break
        leftSize = index - inStart
        root = TreeNode(rootVal)
        root.left = self.build(inorder, inStart, index - 1,
                               postorder, postStart, postStart + leftSize - 1)

        root.right = self.build(inorder, index + 1, inEnd,
                                postorder, postStart + leftSize, postEnd - 1)
        return root

    def buildTree(self, inorder: list, postorder: list) -> TreeNode:
        return self.build(inorder, 0, len(inorder) - 1,
                          postorder, 0, len(postorder) - 1)

    def printTree(self, treeNode: TreeNode):
        if treeNode == None: return '#'

        print(treeNode.val)

        self.printTree(treeNode.left)
        self.printTree(treeNode.right)


if __name__ == "__main__":
    s = Solution()
    a = ListNode(5, None)
    b = ListNode(4, a)
    c = ListNode(3, b)
    d = ListNode(2, c)
    e = ListNode(1, d)
    # print(11 % 5)
    post = [9, 15, 7, 20, 3]
    ino = [9, 3, 15, 20, 7]
    t = s.buildTree(ino, post)
    print(s.printTree(t))
